#include <list.h>
#include "vm/frame.h"
#include "threads/pte.h"
#include "threads/vaddr.h"
#include "threads/thread.h"
#include "threads/palloc.h"
#include "userprog/pagedir.h"
#include "userprog/process.h"

static unsigned supp_page_table_hash_func (struct hash_elem *, void *);
static bool supp_page_table_less_func (struct hash_elem *,
                                       struct hash_elem *, void *);
static void reset_accesed_bits ();

struct list frame_table;		// Frame tables list
struct lock frame_table_lock;	// used for synchronization over frame table
struct hash supp_page_table;	// Page table hash list
struct lock supp_page_table_lock;	// used for synchronization over page table
struct frame_struct *hand;	// Eviction pointer for clock algorithm

void
initialize_frame_tables (void)
{
  list_init (&frame_table);
  hash_init (&supp_page_table, supp_page_table_hash_func,
             supp_page_table_less_func, NULL);
  lock_init (&frame_table_lock);
  lock_init (&supp_page_table_lock);
}

static unsigned
supp_page_table_hash_func (struct hash_elem *e, void *AUX)
{
  struct page_struct *page_struct = hash_entry (e, struct page_struct, elem);
  return hash_int (page_struct->key);
}

static bool
supp_page_table_less_func (struct hash_elem *e1,
                           struct hash_elem *e2, void *AUX)
{
  struct page_struct *ps1 = hash_entry (e1, struct page_struct, elem);
  struct page_struct *ps2 = hash_entry (e2, struct page_struct, elem);
  return ps1->key < ps2->key;
}

/*
 Returns a page table attached to PTE.
 returns NULL is not found
*/
struct page_struct * 
supp_page_table_lookup (uint32_t *pte)
{
  struct page_struct page_struct;
  page_struct.key = (int) pte;
  bool pre_acquired = false;

  if (!lock_held_by_current_thread (&supp_page_table_lock))
  	lock_acquire (&supp_page_table_lock);
  else
	pre_acquired = true;

  struct hash_elem *e = hash_find (&supp_page_table, &page_struct.elem);
  
  if (!pre_acquired)
  	lock_release (&supp_page_table_lock);

  if (e == NULL)
    return NULL;
  else
    return hash_entry (e, struct page_struct, elem); 
}

/*
   Returns a page table entry associated to UPAGE and PAGEDIR
   Returns true if found or create one if CREATE_PDE is true
   Otherwise returns false
*/

uint32_t*
page_table_entry_lookup (uint8_t *upage, uint32_t *pagedir, bool create_pde)
{
  /* Obtain page directory index of the virtual address corresponding to */
  /* upage with respect to pagedir for the current thread */
  uint32_t *pagedir_entry = pagedir + pd_no (upage);
  uint32_t *page_table_entry;
  if (*pagedir_entry == 0)
  {
    if (create_pde)
    {
      page_table_entry = palloc_get_page (PAL_ZERO);
      if (!page_table_entry)
        return NULL;
      *pagedir_entry = pde_create (page_table_entry);
    }
    else
      return NULL;
  }
  
  page_table_entry = pde_get_pt (*pagedir_entry);
  return (page_table_entry + pt_no (upage));
}


/*
  Given the input values, creates a supplementary page table entry
  if one does not exist. If already exist then update it with input values
*/
bool
allocate_page (int pos_flag, int property_flag, int ftype_flag, 
	       bool is_all_zeroes, uint8_t *upage, uint8_t *vaddr, 
	       size_t len, block_sector_t sector_num)
{  
   bool add_to_list = false;
   uint32_t *page_table_entry = page_table_entry_lookup (upage,
                                  thread_current ()->pagedir, true);
   struct page_struct *page_struct = supp_page_table_lookup (page_table_entry);
   
   if (!page_struct)
   {
     page_struct = (struct page_struct *)
                    malloc (sizeof (struct page_struct));
     if (!page_struct)
          return false;
     page_struct->frame = (struct frame_struct *)
                        malloc (sizeof (struct frame_struct));
     if (!page_struct->frame)
     {
       free (page_struct);
       return false;
     }
     add_to_list = true;
   }
   
   page_struct->key = (int) page_table_entry;
   page_struct->frame->pos_flag = pos_flag;
   page_struct->frame->property_flag = property_flag;
   page_struct->frame->type_flag = ftype_flag;
   page_struct->frame->is_all_zeroes = is_all_zeroes;
   page_struct->frame->vaddr = vaddr;
   page_struct->frame->upage = upage;
   page_struct->frame->len = len;
   page_struct->frame->sector_num = sector_num;
   page_struct->frame->t = thread_current ();
   
   if (add_to_list)
   {
     lock_init (&page_struct->frame->frame_lock);

     /* Insert newly allocated frame into the 'FRAME_TABLE' */
     lock_acquire (&frame_table_lock);
     list_push_back (&frame_table, &page_struct->frame->elem);
     lock_release (&frame_table_lock);

     /* Insert newly allocate page into the 'PAGE_TABLE' */
     lock_acquire (&supp_page_table_lock);
     hash_insert (&supp_page_table, &page_struct->elem);
     lock_release (&supp_page_table_lock);
   }
   return true;
}

/*
  Removes the supplementary page table entry associated with the UPAGE
  and free the memory
*/
void
deallocate_page (uint8_t *upage)
{  
   uint32_t *page_table_entry = page_table_entry_lookup (upage,
                                                   thread_current ()->pagedir,
                                                   false);
   struct page_struct *ps = supp_page_table_lookup (page_table_entry);
   
   free_ps (ps);
}

/*
  Removes the PS for supplmentary page table SUPP_PAGE_TABLE
  and also FRAME_TABLE. Free the heap memory.
*/
void free_ps (struct page_struct *ps)
{
  if (ps)
   {
     lock_acquire (&supp_page_table_lock);
     lock_acquire (&frame_table_lock);  
     list_remove (&ps->frame->elem);
     free (ps->frame);
     hash_delete (&supp_page_table, &ps->elem);
     free (ps);
     lock_release (&frame_table_lock);
     lock_release (&supp_page_table_lock);
   }
}

/* 
  Returns the virtual address of the frame to be evicted. 
  Evict frame is chosen based on clock algorithm. HAND decides
  the start point of the evict frame search and the first non-busy,
  in memory frame is selected for eviction.

  Returns NULL if no frame is available for swap out
*/
uint8_t *evict_frame ()
{
  struct list_elem *e;
  struct frame_struct *evict_frame;

  lock_acquire (&frame_table_lock);

  /* Initialize clock hand to first element if NULL */
  if (hand == NULL)
      hand = list_entry (list_begin (&frame_table), struct frame_struct, elem);

  struct frame *start = hand;
  
  while (true)
  {
    evict_frame = hand;
    // Update hand position to point to next element in the list
    e = list_next (&hand->elem);
    if (e == list_end (&frame_table))
      e = list_begin (&frame_table);
    hand = list_entry (e, struct frame_struct, elem);
    
    if (evict_frame->pos_flag == FRAME_IN_MEM 
        && !lock_held_by_current_thread (&evict_frame->frame_lock)
        && lock_try_acquire (&evict_frame->frame_lock))
      break;

    if (hand == start)
	reset_accesed_bits ();
  }

  uint8_t *result = evict_frame->vaddr;
  lock_release (&frame_table_lock);
  
  if (!swap_out (evict_frame))
    return NULL;
  else
    return result;
}

static void reset_accesed_bits ()
{
  ASSERT (lock_held_by_current_thread (&frame_table_lock));

  struct list_elem *e;
  struct frame_struct *f;  

  for (e = list_begin (&frame_table); e != list_end (&frame_table);
        e = list_next (e))
  {
	f = list_entry (e, struct frame_struct, elem);
 	if (f->pos_flag == FRAME_IN_MEM)
		pagedir_set_accessed (f->t->pagedir, f->vaddr, false);
  }
}
